package com.rr.middle;

/**
 * @author RR
 * @date 2024/6/22 16:10
 */

/**
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/
 * 二分查找
 */
public class SearchRange {
    int[] result = new int[]{-1, -1};
    public int[] searchRange(int[] nums, int target) {
        getResult(0, nums.length-1, nums, target);
        return result;
    }

    private void getResult(int left, int right, int[] nums, int target) {
        int index = -1;
        int tmpLeft = left;
        int tmpRight = right;
        while (tmpLeft <= tmpRight) {
            int middle = (tmpLeft + tmpRight) / 2;
            if (nums[middle] == target) {
                index = middle;
                break;
            } else if (nums[middle] > target) {
                tmpRight = middle - 1;
            } else {
                tmpLeft = middle + 1;
            }
        }
        if (index != -1) {
            if (result[0] != -1) {
                result[0] = Math.min(result[0], index);
            }else {
                result[0] = index;
            }
            if (result[1] != -1) {
                result[1] = Math.max(result[1], index);
            } else {
                result[1] = index;
            }
            getResult(left, index-1, nums, target);
            getResult(index + 1, right, nums, target);
        }
    }

    public static void main(String[] args) {
        SearchRange searchRange = new SearchRange();
        int[] ints = searchRange.searchRange(new int[]{5,7,7,8,8,10}, 6);
        System.out.println(ints);
    }

}
